|
The following are examples to supplement the article Turing machine. ==Turing's very first example== The following table is Turing's very first example (Alan Turing 1937): :"1. A machine can be constructed to compute the sequence 0 1 0 1 0 1..." (0 With regard to what actions the machine actually does, Turing (1936) (''Undecidable'' p. 121) states the following: : "This () table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the m-configuration in the final column." (Undecidable p. 121) He makes this very clear when he reduces the above table to a single instruction called "b" (''Undecidable'' p. 120), but his instruction consists of 3 lines. Instruction "b" has three different symbol possibilities . Each possibility is followed by a sequence of actions until we arrive at the rightmost column, where the final m-configuration is "b": As observed by a number of commentators including Turing (1937) himself, (e.g., Post (1936), Post (1947), Kleene (1952), Wang (1954)) the Turing instructions are not atomic — further simplifications of the model can be made without reducing its computational power; see more at Post–Turing machine. As stated in the article Turing machine, Turing proposed that his table be further atomized by allowing only a single print/erase followed by a single tape movement L/R/N. He gives us this example of the first little table converted (''Undecidable'', p. 127): Turing's statement still implies five atomic operations. At a given instruction (m-configuration) the machine: # observes the tape-symbol underneath the head # based on the observed symbol goes to the appropriate instruction-sequence to use # prints symbol Sj or erases or does nothing # moves tape left, right or not at all # goes to the final m-configuration for that symbol Because a Turing machine's actions are not atomic, a simulation of the machine must atomize each 5-tuple into a sequence of simpler actions. One possibility — used in the following examples of "behaviors" of his machine — is as follows: :(qi) Test tape-symbol under head: If the symbol is S0 go to qi.01, if symbol S1 go to qi.11, if symbol S2 go to qi.21, etc. ::(qi.01) print symbol Sj0 or erase or do nothing then go to qi.02 ::(qi.02) move tape left or right nor not at all then go to qm0 ::(qi.11) print symbol Sj1 or erase or do nothing then go to qi.12 ::(qi.12) move tape left or right nor not at all then go to qm1 ::(qi.21) print symbol Sj2 or erase or do nothing then go to qi.22 ::(qi.22) move tape left or right nor not at all then go to qm2 : (etc — all symbols must be accounted for) So-called "canonical" finite state machines do the symbol tests "in parallel"; see more at microprogramming. In the following example of what the machine does, we will note some peculiarities of Turing's models: :"The convention of writing the figures only on alternate squares is very useful: I shall always make use of it." (Undecidable p. 121) Thus when printing he skips every other square. The printed-on squares are called F-squares; the blank squares in between may be used for "markers" and are called "E-squares" as in "liable to erasure." The F-squares in turn are his "Figure squares" and will only bear the symbols 1 or 0 — symbols he called "figures" (as in "binary numbers"). In this example the tape starts out "blank", and the "figures" are then printed on it. For brevity only the TABLE-states are shown here: The same "run" with all the intermediate tape-printing and movements is shown here: A close look at the table reveals certain problems with Turing's own example—not all the symbols are accounted for. For example, suppose his tape was not initially blank. What would happen? The Turing machine would read different values than the intended values. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing machine examples」の詳細全文を読む スポンサード リンク
|